// 根据一棵树的前序遍历与中序遍历构造二叉树。

// 注意:
// 你可以假设树中没有重复的元素。

// 例如，给出

// 前序遍历 preorder = [3,9,20,15,7]
// 中序遍历 inorder = [9,3,15,20,7]
// 返回如下的二叉树：

//     3
//    / \
//   9  20
//     /  \
//    15   7


/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */


// ===================利用preorder的每一个元素都是对应递归子树的根节点==============
var buildTree = function (preorder, inorder) {
  // 全局变量cursor是preorder的指针，随递归移动
  let cursor = 0;
  let buildTree_recursion = (inorder) => {
    if (inorder.length !== 0) {
      let
        // 在preorder中读取根节点
        rootVal = preorder[cursor],
        // 在inorder中寻找根节点的下标，左侧为其左子树，右侧为其右子树
        rootIndex = inorder.indexOf(rootVal),
        root = new TreeNode(rootVal);
      // 每次生成完root都移动cursor
      cursor++;
      if (rootIndex === 0) {
        root.left = null;
        root.right = buildTree_recursion(inorder.slice(rootIndex + 1));
      }
      else if (rootIndex === inorder.length - 1) {
        root.left = buildTree_recursion(inorder.slice(0, rootIndex));
        root.right = null;
      }
      else {
        root.left = buildTree_recursion(inorder.slice(0, rootIndex));
        root.right = buildTree_recursion(inorder.slice(rootIndex + 1));
      }
      return root;
    }
    return null
  }
  return buildTree_recursion(inorder)
};

// ============================传统方法：处理下标===============================
var buildTree = function (preorder, inorder) {
  /*
    参数说明
      preorder：前序数组
      pre_start：构造子树的前序数组段的起始下标
      pre_end：构造子树的数组段的结束下标
      inorder：中序数组
      in_start:构造子树的中序数组段的起始下标
      in_end：构造子树的中数组段的结束下标
   */
  let build = (preorder, pre_start, pre_end, inorder, in_start, in_end) => {
    if (pre_start > pre_end) return null;
    let
      rootVal = preorder[pre_start],
      root = new TreeNode(rootVal),
      rootIndex = inorder.indexOf(rootVal),
      leftSize = rootIndex - in_start;
    root.left = build(preorder, pre_start + 1, pre_start + leftSize, inorder, in_start, rootIndex - 1);
    root.right = build(preorder, pre_start + leftSize + 1, pre_end, inorder, rootIndex + 1, in_end);
    return root;
  }
  return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1)
};